﻿ #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
	string multiply(string num1, string num2) {
		// 1. 特殊情况处理，如果有一个是0，结果肯定是0
		if (num1 == "0" || num2 == "0")
			return "0";
		// 2. 保证num1比num2短，将来使用num1作为外循环
		int LSize = num1.size();
		int RSize = num2.size();
		if (LSize > RSize)
		{
			num1.swap(num2);
			swap(LSize, RSize);
		}
		// 3. LSize位 * RSize位，结果最多有LSIze+RSize位，比如：99*99 结果最多为4位
		string strRet(LSize + RSize, '0');
		// 4. 用字符串模拟乘法运算：从num1中取一位，与num2中的每一位相乘，乘完之后结果与上一趟相加int oﬀset = 0; // 相加的时候注意偏移
		for (int i = LSize - 1; i >= 0; --i)
		{
			// 取到num1的每一位
			int data = num1[i] - '0';
			char step = 0;
			int retIdx = strRet.size() - 1 - oﬀset;
			for (int j = RSize - 1; j >= 0; --j)
			{
				// 使用data与num2的每一位从右往左依次相乘，错位加上上一次结果
				int ret = (num2[j] - '0') * data;
				ret = ret + strRet[retIdx] - '0';
				step = 0;
				if (ret >= 10)
				{
					step = ret / 10;
					ret %= 10;
				}
				strRet[retIdx] = ret + '0'; // 结果保存在当前位
				strRet[retIdx - 1] += step; // 进位需与前一位相加
				retIdx--;
			}
			// 下一趟需要往前偏移一位相加
			oﬀset++;
		}
		// 如果结果中多了一位，将前置的0删除掉
		if (strRet[0] == '0')
			strRet.erase(strRet.begin());
		return strRet;
	}
};